package com.cty.ThirtyFirstDay;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/*
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
*/
public class Q_52 {
    //bfs 过了 主包自己写的 时间复杂度O(MN) 空间复杂度 O(MN)(最坏的情况下全部都是坏的橘子)
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        //创建一个队列
        Queue<int[]> queue = new LinkedList<>();
        int ans = 0;
        int rowLen = grid.length;
        int colLen = grid[0].length;
        for (int i = 0;i < rowLen;i++) {
            for (int j = 0;j < colLen;j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i,j});
                }
            }
        }
        while (!queue.isEmpty()) {
            ans++;
            int size = queue.size();
            while (size > 0) {
                int[] poll = queue.poll();
                int x = poll[0];
                int y = poll[1];
                if (x + 1 < rowLen && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    queue.offer(new int[]{x+1,y});
                }
                if (y + 1 < colLen && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    queue.offer(new int[]{x,y+1});
                }
                if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    queue.offer(new int[] {x-1,y});
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    queue.offer(new int[] {x,y-1});
                }
                size--;
            }
        }
        for (int i = 0;i < rowLen;i++) {
            for (int j = 0;j < colLen;j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        if (ans > 0) {
            ans--;
        }
        return ans;
    }

    // 力扣官方题解 方法一:多源广度优先搜索
    /*
    * 思路：
    *   用一个哈希表来表示当前橘子腐烂的深度
    *   其他于dfs一样
    * 时间复杂度O(MN) 空间复杂度O(MN)
    * */
    int[] dR = {-1,0,1,0};
    int[] dC = {0,1,0,-1};
    public int orangesRotting2(int[][] grid) {
        if (grid == null || grid.length == 0)return 0;
        int R = grid.length,C = grid[0].length;
        // 用来存储坐标 x * C + y（计算方法）
        Queue<Integer> queue = new LinkedList<>();
        // 用来记录深度的
        HashMap<Integer,Integer> depth = new HashMap<>();
        for (int i = 0;i < R;i++) {
            for (int j = 0;j < C;j++) {
                if (grid[i][j] == 2) {
                    int code = i * C + j;
                    queue.offer(code);
                    depth.put(code,0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            int x = poll / C;
            int y = poll % C;
            for (int i = 0;i < 4;i++) {
                int nx = x + dR[i];
                int ny = y + dC[i];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    int nCode = nx * C + ny;
                    queue.offer(nCode);
                    depth.put(nCode,depth.get(poll) + 1);
                    ans = depth.get(nCode);
                }
            }
        }
        for (int i = 0;i < R;i++) {
            for (int j = 0;j < C;j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}
